/**
 * @description 图类
 * @see https://blog.csdn.net/IAIPython/article/details/132059073
 * @date 2024-11-03
 */
class Graph<T> {
  vertexes: T[] = [] // 存储顶点
  adjList: Map<T, T[]> = new Map() // 存储邻接表

  /**
   * 添加顶点
   * @param vertex 图的顶点
   */
  addVertex(vertex: T) {
    this.vertexes.push(vertex) // 添加顶点
    this.adjList.set(vertex, []) // 添加邻接表
  }

  /**
   * 添加边
   * @param vertex1 图的顶点1
   * @param vertex2 图的顶点2
   */
  addEdge(vertex1: T, vertex2: T) {
    this.adjList.get(vertex1)?.push(vertex2) // 添加边
    this.adjList.get(vertex2)?.push(vertex1) // 添加边
  }

  toString() {
    this.vertexes.forEach((vertex) => {
      console.log(vertex + ' -> ' + this.adjList.get(vertex)?.join(' ')) // 打印邻接表
    })
  }

  /**
   * 广度优先遍历
   * @returns 返回图的顶点
   */
  BFS() {
    if (this.vertexes.length === 0) return // 如果没有顶点 则返回
    const visited = new Set<T>() // 用于存储已经访问过的顶点
    visited.add(this.vertexes[0]) // 从第一个顶点开始遍历
    const queue = [this.vertexes[0]] // 用于存储待访问的顶点

    // 队列不为空时
    while (queue.length) {
      const v = queue.shift()! // 取出队列的第一个顶点
      console.log(v) // 打印顶点

      const vEdges = this.adjList.get(v) // 获取该顶点的邻接表
      // 如果没有邻接表 则跳过
      if (!vEdges) continue
      // 从前往后遍历
      for (const e of vEdges) {
        // 如果没有访问过 就入队列
        if (!visited.has(e)) {
          visited.add(e)
          queue.push(e)
        }
      }
    }
  }

  /**
   * 深度优先遍历
   * @returns 返回图的顶点
   */
  DFS() {
    if (this.vertexes.length === 0) return // 如果没有顶点 则返回
    const visited = new Set<T>() // 用于存储已经访问过的顶点
    visited.add(this.vertexes[0]) // 从第一个顶点开始遍历
    const stack = [this.vertexes[0]] // 用于存储待访问的顶点

    // 栈不为空时
    while (stack.length) {
      const v = stack.pop()! // 取出栈顶的顶点
      console.log(v) // 打印顶点

      const vEdges = this.adjList.get(v) // 获取该顶点的邻接表
      if (!vEdges) return // 如果没有邻接表 则跳过
      // 从后往前遍历
      for (let i = vEdges.length - 1; i >= 0; i--) {
        const e = vEdges[i] // 获取顶点
        // 如果没有访问过 就入栈
        if (!visited.has(e)) {
          stack.push(e)
          visited.add(e)
        }
      }
    }
  }
}

export default Graph
